package Java1Test;

// 二分查找算法实现
public class BinarySearch {
    public static void main(String[] args) {
        // 待查找的有序数组
        int[] arr = {1, 2, 3, 4, 5};
        // 要查找的目标元素
        int number = 4;
        // 调用二分查找方法并输出结果
        System.out.println("元素 " + number + " 在数组中的索引位置是: " + binarySearch(number, arr));
    }


    /**
     * 二分查找指定元素在有序数组中的索引位置
     * @param number 要查找的目标元素
     * @param arr 待查找的有序数组(必须是升序排列)
     * @return 如果找到返回元素索引，如果未找到返回-1
     */
    public static int binarySearch(int number, int[] arr) {
        // 搜索范围的左边界(最小索引)
        int min = 0;
        // 搜索范围的右边界(最大索引)
        int max = arr.length - 1;

        // 循环进行二分查找，直到搜索范围为空
        while (true) {
            // 当最小索引大于最大索引时，表示搜索范围为空，元素不存在
            if (min > max) {
                return -1;
            }

            // 计算中间位置索引
            int mid = (max + min) / 2;

            // 比较目标元素与中间元素的大小
            if (number < arr[mid]) {
                // 目标元素小于中间元素，缩小右边界到中间位置前一个位置
                max = mid - 1;
            } else if (number > arr[mid]) {
                // 目标元素大于中间元素，扩大左边界到中间位置后一个位置
                min = mid + 1;
            } else {
                // 找到目标元素，返回中间位置索引
                return mid;
            }
        }
    }
}